"""给你一个整数 n ，请你找出并返回第 n 个 丑数 。

说明：丑数是只包含质因数 2、3 和/或 5 的正整数；1 是丑数。

 

示例 1：

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
提示： 

1 <= n <= 1690
 

注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/"""
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> res(n);
        res[0] = 1;
        int a = 0;
        int b = 0; 
        int c = 0;
        for (int i = 1; i < n; ++i) {
            int n2 = res[a] * 2;
            int n3 = res[b] * 3;
            int n5 = res[c] * 5;
            res[i] = min(min(n2, n3), n5);
            if (res[i] == n2) a++;
            if (res[i] == n3) b++;
            if (res[i] == n5) c++;
        }
        return res[n-1];
    }
};